//
//  Graph.hpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/7/30.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef Graph_hpp
#define Graph_hpp

#include <stdio.h>
#define Max_Size 100

// G = (V,E)：V顶点集非空，E边集可以为空
// 简单图和多重图
// 度；入度和出度
// 路径：顶点序列
// 简单路径：无重复顶点
// 回路（环）：第一个顶点和最后一个顶点相同
// 简单回路：无重复顶点
// 路径长度：边的数量
// 点到点的距离：最短路径 \ ∞
// 连通：无向图中有v到w路径存在，则v和w连通
// 强连通：有向图中v到w和w到v的路径都存在，则v和w强连通
// 连通图：任意顶点都是连通的（最少边：串；非连通的最多边C_{n-1}^{2}）
// 强连通图：任意顶点都是强连通的（最少边：环）
// 子图 / 生成子图
// 连通分量：极大连通子图
// 强连通分量：极大强连通子图
// 生成树：包含全部顶点的极小连通子图
// 生成森林：非连通图的生成树组成的森林
// 边的权
// 带权图/网
// 带权路径长度
// 无向完全图：任意2个顶点都存在边（边的总数：C_{n}^{2}）
// 有向完全图：任意2个顶点都存在2条方向相反的边（边的总数：2C_{n}^{2}）
// 树：不存在回路且连通的无向图
// 有向树：只有1个结点的入度为0，其余顶点入度都为1

// **** 邻接矩阵法 ****
// 出入度时间复杂度：O(V)
// 空间复杂度：O(V^2)
// 适合稠密图 / 无向图使用矩阵压缩法
// 矩阵A^n中A[i][j]表示i到j路径长度为n路径的数量
// 邻接矩阵唯一
typedef struct {
    char Vex[Max_Size];
    int Edge[Max_Size][Max_Size];
    int vexnum, arcnum;
} MGraph;

// **** 邻接表法（顺序+链式） ****
// 适合稀疏图
// 无向图空间复杂度：O(V + 2E)
// 有向图空间复杂度：O(V + E)
// 无向图的度：遍历边表
// 有向图出度：遍历边表
// 有向图入度：遍历所有边表（效率低下）
// 无向图删除顶点和边不方便
// 邻接表不唯一
typedef struct ArcNode { // 边
    int adjvex; // 指向某个顶点
    struct ArcNode *nextarc; // 指向下一条边
} ArcNode;

typedef struct VNode { // 顶点
    char data; // 顶点信息
    ArcNode *firstarc; // 第一条边
} VNode, AdjList[Max_Size];

typedef struct {
    AdjList vertex; // 顶点
    int vexnum, arcnum;
} ALGraph;

// *** 十字链表（有向图） ***
// 空间复杂度：O(V+E)
// 找出入度都方便

// *** 邻接多重表（无向图）***
// 空间复杂度O(V+E)
// 删除边和结点方便

// ***** 图的基本操作 *****
// 1. Adjacent(G,x.y)判断是否存在边
// 有向图和无向图
// 邻接矩阵法：O(1)
// 邻接表法：O(1)~O(V)
// 2. Neighbors(G,x)顶点x找到邻接的边
// 有向图
// 邻接矩阵法：O(V)
// 邻接表法：O(1)~O(V)
// 无向图
// 邻接矩阵法：O(V)
// 邻接表法：入边：O(E) 出边O(V)
// 3. InsertVertex(G,x)插入顶点x
// 无向图和有向图
// 邻接矩阵法：O(1)
// 邻接表法：O(1)
// 4. DeleteVertex(G,x) 删除顶点
// 无向图和有向图
// 邻接矩阵法：O(V)
// 邻接表法：O(1)~O(E)
// 5. AddEdge(G,x,y)增加一条边
// 无向图和有向图
// 邻接矩阵法：O(1)
// 邻接表法：O(1)
// 6. ✨FirstNeighborhood(G,x)找到x第一个邻接的顶点
// 无向图
// 邻接矩阵法：O(1)~O(V)
// 邻接表法：O(1)
// 有向图
// 邻接矩阵法：O(1)~O(V)
// 邻接表法：出O(1) 入O(1)~O(E)
// 7. ✨NextNeighborhood(G,x,y)找到x下一个结点y的下一个结点
// 无向图和有向图
// 邻接矩阵法：O(V)
// 邻接表法：O(1)
// 8. 给边设置权值
// 无向图和有向图
// 邻接矩阵法：O(1)
// 邻接表法：O(1)~O(V)

// ***** 图的广度优先遍历 *****
/**
 bool visited[MAX_VERTEX_NUM]; // 都设为0
 // 广度优先遍历
 // 空间复杂度：O(V)
 // 时间复杂度：邻接矩阵O(V^2) 邻接表O(V + E) (这里需要理解，不要钻到代码里看)
 void BFS(Graph G, int v)
 {
    visit(v);
    visited[v] = true;
    EnQueue(Q, v);
    while (!EmptyQueue(Q)) {
        DeQueue(Q, v);
        for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            if (!visited[w]) {
                visit(w);
                visited[w] = true;
                EnQueue(Q, w);
            }
        }
    }
 }
 // 为了让非连通的图也能全部遍历，需要检查visited数组中是否都为true
 void BFSTraverse(Graph G, int v) {
    for (int i = 1; i <= MAX_VERTEX_NUM; i++)
        if (!visited[i])
            BFS(Graph G, i); // ✨调用次数 = 非连通图的个数
 }
 */

// *** 广度优先生成树（借助队列生成） ***
// 邻接表的生成树不唯一

// *** 广度优先生成森林 ***
// 非连通的图生成森林

// ***** 图的深度优先遍历 *****
// 类似树的先根遍历
// 空间复杂度：O(V)
// 时间复杂度：邻接矩阵法：O(V^2) 邻接表法：O(V + E)
/**
 bool visited[MAX_VERTEX_NUM]; // 全部设为false
 void DFS(Graph G, int v) {
    visit(v);
    visited[v] = true;
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w])
            DFS(G, w);
    }
 }
 void DFSTraverse(Graph G, int v) {
    for (int i = 1; i <= MAX_VERTEX_NUM; i++)
        if (!visited[i])
            DFS(G, i);
 }
 */

// *** 深度优先生成树（借助栈生成） ***
// 邻接表的生成树不唯一

// ✨最小生成树和最短路径区别
// 最小生成树：修最短的路
// 最短路径：1.P城到G港的最短路径；2.所有点间的最短路径

// ***** 最小生成树(MST)（不唯一）（手算^_^） *****
// Prim算法 从一个结点出发，选结点和结点最短的结点O(V^2)，适合稠密图
// Kruskal算法 从最短的边出发，选最小短的边，边需要非连通O(Elog2(E))，适合稀疏图

// ***** 最短路径 *****
// 单源最短路径
// BFS广度优先算法计算最短路径（✨不带权图）
// dist[]
// path[]
/**
 void BFS_MIN_Distance(Graph G, int u)
 {
    for (i = 0; i < G.vexnum; i++) {
        d[i] = ∞; // 距离
        path[i] = -1; // 从哪个顶点过来的
    }
    d[u] = 0;
    visited[u] = true;
    EnQueue(Q, u);
    while(!Empty(Q)){
        DeQueue(Q, u);
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
            if (!visited[w]) {
                d[w] = d[u] + 1;
                path[w] = u;
                visited[w] = true;
                EnQueue(Q, w);
            }
        }
    }
 }
*/

// Dijkstra算法 （带权图）O(V^2)
// 从v0开始，初始化下列数组
// final[]
// dist[]
// path[]

// Floyd算法（带权图）
// O(V^3)
void Floyd()
{
    int n = 3;
    int A[3][3], path[3][3];
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i][j] > A[i][k] + A[k][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

// *** 有向无环图DAG ***
// GAD描述表达式问题：使用最少结点来描述表达式,是不唯一的
// AOV网 Activity On Vertex Nextwork（有向无环图）：顶点表示活动，边表示活动的发生顺序
// 拓扑排序：找到做事的先后顺序
// 邻接表法：O(V+E)邻接矩阵法：O(V^2)
// 1. 删除入度为0的顶点
// 2. 删除从顶点出发的边
// 3. 重复1和2，直到前部结点被删除，或者没有无前驱结点的顶点为止
/**
 各个顶点的入度：indegree[]
 打印顺序：print[]
 bool TopologicalSort(Graph G)
 {
    InitStack(S);
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i] == 0) {
            Push(S, i);
        }
    }
    int count = 0;
    while(!Empty(S)) {
        Pop(S, i);
        print[count++] = i;
        for (p = G.vertices[i].firstarc;p;p=p->nextarc) {
            v = p->adjvex;
            if (!(--indegree[v])) {
                Push(S, v);
            }
        }
    }
    return count == G.vexnum;
 }
 */

// ** 逆拓扑排序 **
// 删除出度为0的顶点

// *** DFS实现逆拓扑排序 ***
// 在深度优先遍历最后输出顶点即可
// 如果访问2次同一个结，说明拓扑排序失败！存在环路。

// ***** AOE网 Activity On Edge Network *****
// 关键路径
// 用边来表示活动，顶点表示事件
// 源点：AOE网中仅存在一个入度为0的顶点，它代表整个工程的开始
// 汇点：AOE网中仅存在一个出度为0的顶点，它代表整个工程的结束
// 关键路径：从源点到汇点的最大长度的路径
// 关键活动：关键路径上的活动(优化它们可以缩减整个工程)
// 整个工程的最短时间：关键路径长度

// ***** 求关键路径的步骤 *****
// 1. 求所有事件的最早开始时间ve() 拓扑排序
// 2. 求所有事件的最迟开始时间vl() 逆拓扑排序
// 3. 求所有活动最早发生时间e() = ve()
// 4. 求所有活动最迟发生时间l()
// 5. 求所有活动的时间余量d，d(i) == 0 说明这是关键活动
// 把所有关键路径的时间都缩短，可以减少工程完成的时间
#endif /* Graph_hpp */
